package com.leetcodehot.problems;

import java.util.ArrayDeque;
import java.util.Deque;

public class problems1696 {


    public int maxResult(int[] nums, int k) {
        /**
         * 只需要维护res 的滑动数组最大值即可，i视为当前从0到i的最大分数
         */
        int n = nums.length;
        int[] res = new int[n];
        res[0] = nums[0];
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            if (!q.isEmpty() && i - q.getFirst() > k) {
                q.removeFirst();
            }
            if(q.isEmpty()){
                res[i] = nums[i];
            }else{
                res[i] = res[q.getFirst()] + nums[i];
            }
            while (!q.isEmpty() && res[q.getLast()] <= res[i]) {
                q.removeLast();
            }
            q.addLast(i);
        }
        return res[n - 1];
    }
}
